package com.cdream.basic.algorithm.leetcode.linkedlist;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author cdream
 * @date 7/7/21
 */
public class Question1711 {
    public int countPairs(int[] deliciousness) {
        Set<Integer> s = new HashSet<Integer>();
        s.add(1);
        int k = 1;
        for(int i =1;i<=21;i++){
            k *=2;
            s.add(k);
        }
        int count = 0;
        int MOD = 1000000000 + 7;
        Map<Integer,Integer> map= new HashMap<>();
        for(int i =0;i<deliciousness.length;i++){
            for(int j : s){
                Integer v = map.get(j-deliciousness[i]);
                if(v!=null){
                    count = (count+v) % MOD;
                }
            }
            map.put(deliciousness[i],map.getOrDefault(deliciousness[i],0)+1);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(new Question1711().countPairs(new int[]{1, 3, 5, 7, 9}));
    }
}
